package design;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/4/5
 * @verdion 1.0.0
 * 244. 最短单词距离 II
 * 请设计一个类，使该类的构造函数能够接收一个单词列表。然后再实现一个方法，该方法能够分别接收两个单词 word1 和 word2，并返回列表中这两个单词之间的最短距离。您的方法将被以不同的参数调用 多次。
 *
 * 示例:
 * 假设 words = ["practice", "makes", "perfect", "coding", "makes"]
 *
 * 输入: word1 = “coding”, word2 = “practice”
 * 输出: 3
 * 输入: word1 = "makes", word2 = "coding"
 * 输出: 1
 * 注意:
 * 你可以假设 word1 不等于 word2, 并且 word1 和 word2 都在列表里。
 */
public class WordDistance {
    Map<String, List<Integer>> map;
    public WordDistance(String[] words) {
        map = new HashMap<>();
        for(int i = 0; i < words.length; i ++){
            map.computeIfAbsent(words[i], x -> new ArrayList<>()).add(i);
        }
        for(List<Integer> l: map.values()){
            Collections.sort(l);
        }
    }

    public int shortest(String word1, String word2) {
        if(word1 == null || word2 == null || word1.length() == 0 || word2.length() == 0){
            return 0;
        }
        List<Integer> l1 = map.get(word1);
        List<Integer> l2 = map.get(word2);
        if(l1.size() > l2.size()){
            return findMin(l2, l1);
        }
        return findMin(l1, l2);
    }

    private int findMin(List<Integer> l1, List<Integer> l2){
        int min = Integer.MAX_VALUE;
        for(int i: l1){
            int l = 0;
            int r = l2.size();
            while(l < r){
                int mid = (l + r) /2;
                if(i > l2.get(mid)){
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            if(l == l2.size()){
                l = l2.size() - 1;
            }
            int dis = Math.abs(l2.get(l) - i);
            if(l > 0 && l < l2.size()){
                dis = Math.min(dis, Math.abs(l2.get(l - 1) - i));
            }
            if(dis < min){
                min = dis;
            }
        }
        return min;
    }
}
